#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    /*
     * @param s: input string
     * @return: the longest palindromic substring
     */
    string longestPalindrome(string &s) {
        // write your code her
        int len = s.size();
        if( len <=0 )
            return "";

        int maxlen = 1;
        int pos = 0;
        bool **dp = new bool *[len];
        for( int i = 0; i < len; i++ ){
            dp[i] = new bool [len];
        }

        for(int i = 0; i < len; i++)
            dp[i][i] = true;

        for(int i = 0; i < len - 1; i++){
            dp[i][i+1] = (s[i] == s[i+1]);
            if( dp[i][i+1] && maxlen == 1 ){
                maxlen = 2;
                pos = i;
            }
        }

        for( int i = len - 2; i >= 0; i--){
            for( int j = i + 2; j < len; j++){
                if( s[i] == s[j] ){
                    if( dp[i+1][j-1] ){
                        dp[i][j] = true;
                        if( j - i + 1 > maxlen ){
                            maxlen = j - i + 1;
                            pos = i;
                        }
                    }
                    else
                        dp[i][j] = false;
                }else
                    dp[i][j] = false;
            }
        }


        for( int i = 0; i < len; i++)
            delete [] dp[i];
        delete [] dp;
        
        return s.substr(pos, maxlen);
    }
};